Concepedia

Concept

problem reduction

Parents

281

Publications

28.5K

Citations

540

Authors

283

Institutions

About

Problem reduction is a fundamental concept and methodological approach in computer science, artificial intelligence, and complexity theory. It involves transforming a given complex problem into one or more simpler sub-problems, or demonstrating its solvability through transformation into another known problem. This technique investigates how problems can be decomposed, mapped, or related to facilitate analysis, algorithm design, and classification based on computational difficulty. Its key characteristics include the definition of transformation rules between problem instances and the establishment of a relationship ensuring that a solution to the reduced problem(s) implies a solution to the original. The significance of problem reduction lies in its role as a powerful strategy for developing algorithms, navigating search spaces in artificial intelligence, and establishing hierarchies within computational complexity theory, particularly in defining classes like NP-completeness.

Top Authors

Rankings shown are based on concept H-Index.

FG

University of Colorado Boulder

EB

Carnegie Mellon University

MP

New York University

MF

University of Padua

BC

Pontificia Universidad Católica de Valparaíso

Top Institutions

Rankings shown are based on concept H-Index.

Pittsburgh, United States

University of Michigan

Ann Arbor, United States

Stanford University

Stanford, United States

University of California, Berkeley

Berkeley, United States